package special.graph;

public class FloydWarshallAlgorithm {
    public static void main(String[] args) {
        // 一个带权重的图的邻接矩阵表示
        int[][] graph = {
                {0, 5, Integer.MAX_VALUE, 10},
                {Integer.MAX_VALUE, 0, 3, Integer.MAX_VALUE},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, 0, 1},
                {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };

        int[][] shortestDistances = floydWarshall(graph);

        // 打印最短路径矩阵
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                if (shortestDistances[i][j] == Integer.MAX_VALUE) {
                    System.out.print("INF ");
                } else {
                    System.out.print(shortestDistances[i][j] + "   ");
                }
            }
            System.out.println();
        }
    }

    public static int[][] floydWarshall(int[][] graph) {
        int numNodes = graph.length;
        int[][] shortestDistances = new int[numNodes][numNodes];

        // 初始化最短路径矩阵
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                shortestDistances[i][j] = graph[i][j];
            }
        }

        // 逐步计算最短路径
        for (int k = 0; k < numNodes; k++) {
            for (int i = 0; i < numNodes; i++) {
                for (int j = 0; j < numNodes; j++) {
                    // 如果从节点i到节点j经过节点k的路径更短，更新最短路径
                    if (shortestDistances[i][k] != Integer.MAX_VALUE &&
                            shortestDistances[k][j] != Integer.MAX_VALUE &&
                            shortestDistances[i][k] + shortestDistances[k][j] < shortestDistances[i][j]) {
                        shortestDistances[i][j] = shortestDistances[i][k] + shortestDistances[k][j];
                    }
                }
            }
        }

        return shortestDistances;
    }
}
